/*
 * Copyright 北京航空航天大学 @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * <p>
 * 查找从根结点到叶节点为定值的所有路径
 * Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum. 
 *   例如，输入sum = 22
 *            5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1
         return
        [
           [5,4,11,2],
           [5,8,4,5]
        ]
 * </p>
 * 
 * @author towan
 * @email tongwenzide@163.com 2015年5月18日
 */
public class PathSumII {
    /**
     * 返回给定和的所有路径
     * @param root 
     * @param sum
     * @return
     * @author towan
     * 2015年5月18日
     */
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        //边界条件判定
        if (root == null){
            return result;
        } 
        
        ArrayList<Integer> path = new ArrayList<Integer>();
        path.add(root.val);
        //查看子路径
        findPathSum(root, sum - root.val, path, result);
        return result;
    }
    //查找路径和
    private void findPathSum(TreeNode root, int sum, ArrayList<Integer> path,
            List<List<Integer>> result) {
        //需要再次判断一下，因为递归会调用
        if (root == null) {
            return;
        }
        //根到叶节点满足情况
        if (root.left == null && root.right == null && sum == 0) {
            //满足条件
            result.add(new ArrayList<Integer>(path));
            return;
        }
        //左子树
        if (root.left != null) {
            path.add(root.left.val);
            findPathSum(root.left, sum - root.left.val, path, result);
            //路径回退
            path.remove(path.size() - 1);
        }
        if (root.right != null) {
            path.add(root.right.val);
            findPathSum(root.right, sum - root.right.val, path, result);
            path.remove(path.size() - 1);
        }
    }

    public static void main2(String[] args) {
        TreeNode root = new TreeNode(5);
        TreeNode lRoot = new TreeNode(4);
        TreeNode rRoot = new TreeNode(8);
        root.left = lRoot;
        root.right = rRoot;

        TreeNode lNode = new TreeNode(11);
        lRoot.left = lNode;
        lNode.left = new TreeNode(7);
        lNode.right = new TreeNode(2);

        TreeNode rrNode = new TreeNode(4);
        rRoot.left = new TreeNode(13);
        rRoot.right = rrNode;

        rrNode.left = new TreeNode(5);
        rrNode.right = new TreeNode(1);
        PathSumII pathSumII = new PathSumII();
        System.out.println(pathSumII.pathSum(root, 22));
    }
    
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        PathSumII pathSumII = new PathSumII();
        System.out.println(pathSumII.pathSum(root, 0));
    }
}
